{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## _*Using Qiskit Aqua for clique problems*_\n",
    "\n",
    "This Qiskit Aqua Optimization notebook demonstrates how to use the VQE quantum algorithm to compute the clique of a given graph. \n",
    "\n",
    "The problem is defined as follows. A clique in a graph $G$ is a complete subgraph of $G$. That is, it is a subset $K$ of the vertices such that every two vertices in $K$ are the two endpoints of an edge in $G$. A maximal clique is a clique to which no more vertices can be added. A maximum clique is a clique that includes the largest possible number of vertices. \n",
    "\n",
    "We will go through two examples to show:\n",
    "1. How to run the optimization.\n",
    "2. How how to run the optimization with the VQE.\n",
    "\n",
    "Note that the solution may not be unique."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "####  The problem and a brute-force method."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "\n",
    "from qiskit import BasicAer\n",
    "from qiskit.optimization.applications.ising import clique\n",
    "from qiskit.optimization.applications.ising.common import random_graph, sample_most_likely\n",
    "from qiskit.aqua.algorithms import NumPyMinimumEigensolver"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "first, let us have a look at the graph, which is in the adjacent matrix form."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[ 0.  4.  5.  3. -5.]\n",
      " [ 4.  0.  7.  0.  6.]\n",
      " [ 5.  7.  0. -4.  0.]\n",
      " [ 3.  0. -4.  0.  8.]\n",
      " [-5.  6.  0.  8.  0.]]\n"
     ]
    }
   ],
   "source": [
    "K = 3  # K means the size of the clique\n",
    "np.random.seed(100)\n",
    "num_nodes = 5\n",
    "w = random_graph(num_nodes, edge_prob=0.8, weight_range=10)\n",
    "print(w) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let us try a brute-force method. Basically, we exhaustively try all the binary assignments. In each binary assignment, the entry of a vertex is either 0 (meaning the vertex is not in the clique) or 1 (meaning the vertex is in the clique). We print the binary assignment that satisfies the definition of the clique (Note the size is specified as K)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Solution is  [1, 0, 0, 1, 1]\n"
     ]
    }
   ],
   "source": [
    "def brute_force():\n",
    "    # brute-force way: try every possible assignment!\n",
    "    def bitfield(n, L):\n",
    "        result = np.binary_repr(n, L)\n",
    "        return [int(digit) for digit in result]\n",
    "\n",
    "    L = num_nodes  # length of the bitstring that represents the assignment\n",
    "    max = 2**L\n",
    "    has_sol = False\n",
    "    for i in range(max):\n",
    "        cur = bitfield(i, L)\n",
    "        cur_v = clique.satisfy_or_not(np.array(cur), w, K)\n",
    "        if cur_v:\n",
    "            has_sol = True\n",
    "            break\n",
    "    return has_sol, cur\n",
    "\n",
    "has_sol, sol = brute_force()\n",
    "if has_sol:\n",
    "    print(\"Solution is \", sol)\n",
    "else:\n",
    "    print(\"No solution found for K=\", K)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "qubit_op, offset = clique.get_operator(w, K)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Part I: Run the optimization using the programmatic approach\n",
    "\n",
    "Here we directly construct the algorithm and then run() it to get the result."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Solution is [1 0 1 1 0]\n"
     ]
    }
   ],
   "source": [
    "# We will use the qubit_op and offset from above\n",
    "\n",
    "algo = NumPyMinimumEigensolver(qubit_op)\n",
    "result = algo.run()\n",
    "\n",
    "x = sample_most_likely(result.eigenstate)\n",
    "ising_sol = clique.get_graph_solution(x)\n",
    "if clique.satisfy_or_not(ising_sol, w, K):\n",
    "    print(\"Solution is\", ising_sol)\n",
    "else:\n",
    "    print(\"No solution found for K=\", K)     "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Part II: Run the optimization with the VQE"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can create the objects directly ourselves too and run VQE for the result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Solution is [1. 1. 1. 0. 0.]\n"
     ]
    }
   ],
   "source": [
    "from qiskit.aqua import aqua_globals\n",
    "from qiskit.aqua.algorithms import VQE\n",
    "from qiskit.aqua.components.optimizers import COBYLA\n",
    "from qiskit.circuit.library import TwoLocal\n",
    "\n",
    "aqua_globals.random_seed = 10598\n",
    "\n",
    "optimizer = COBYLA()\n",
    "var_form = TwoLocal(qubit_op.num_qubits, 'ry', 'cz', reps=5, entanglement='linear')\n",
    "vqe = VQE(qubit_op, var_form, optimizer)\n",
    "\n",
    "backend = BasicAer.get_backend('statevector_simulator')\n",
    "result = vqe.run(backend)\n",
    "\n",
    "x = sample_most_likely(result.eigenstate)\n",
    "ising_sol = clique.get_graph_solution(x)\n",
    "\n",
    "if clique.satisfy_or_not(ising_sol, w, K):\n",
    "    print(\"Solution is\", ising_sol)\n",
    "else:\n",
    "    print(\"No solution found for K=\", K)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
